package com.jxm.sort;

import java.util.Arrays;

/**
 * @Author: jxm
 * @Description: 归并排序api设计
 * @Date: 2022/6/9 16:08
 * @Version: 1.0
 */
public class Merge {

    private static Comparable[] assist;//归并所需要的辅助数组

    /**
     * 对数组内的元素进行排序
     * @param a
     */
    public static void sort(Comparable[] a){
        //初始化辅助数组
        assist = new Comparable[a.length];
        //定义 lo 变量和 hi 变量，分别记录数组中的最小索引和最大索引
        int lo = 0;
        int hi = a.length - 1;
        //排序
        sort(a,lo,hi);
    }

    /**
     * 对数组a中从索引lo到索引hi之间的元素进行排序
     * @param a
     * @param lo
     * @param hi
     */
    private static void sort(Comparable[] a, int lo, int hi){
        //做安全检查
        if(hi <= lo){
            return;
        }
        //对lo到hi之间的数据进行分为两个组
        int mid = lo+(hi-lo)/2;
        //分别对每一组数据进行排序
        sort(a,lo,mid);
        sort(a,mid+1,hi);

        //再把两个组中的数据进行归并
        merge(a,lo,mid,hi);
    }

    /**
     * 从索引lo到所以mid为一个子
     * 组，从索引mid+1到索引hi为另一个子组，把数组a中的这两个子组的数据合并成一个有序的大组（从
     * 索引lo到索引hi）
     * @param a
     * @param lo
     * @param mid
     * @param hi
     */
    private static void merge(Comparable[] a, int lo, int mid, int hi){

        //定义三个指针
        int i = lo;
        int p1 = lo;
        int p2 = mid+1;

        //遍历，移动p1指针和p2指针，比较对应索引必的值，找出小的那个，放到辅助数组的对应索引处
        while (p1<=mid && p2<=hi){
            //比较对应索引处的值
            if(less(a[p1],a[p2])){
                assist[i++] = a[p1++]; //++是表示填充值过后指针往后移动一位
            }else {
                assist[i++] = a[p2++];
            }
        }

        //遍历，如果p1的指针没有走完，那么顺序移动p1指针，把对应的元素放到辅助数组的对应索引处
        while (p1 <= mid){
            assist[i++] = a[p1++];
        }

        //遍历，如果p2的指针没有走完，那么顺序移动p2指针，把对应的元素放到辅助数组的对应索引处
        while (p2 <= hi) {
            assist[i++] = a[p2++];
        }

        //把辅助数组中的元素拷贝到原数组中
        for (int index = lo;index <= hi;index++){
            a[index] = assist[index];
        }

    }

    /**
     * 判断vw
     * @param v
     * @param w
     * @return
     */
    private static boolean less(Comparable v,Comparable w){
        return v.compareTo(w)<0;
    }

    /**
     * 交换a数组中，索引i和索引j处的值
     * @param a
     * @param i
     * @param j
     */
    private static void exch(Comparable[] a,int i,int j){
        Comparable temp;
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    //最坏情况下：时间复杂度为O(nlogn);
    //但需要申请额外的数组空间，导致空间复杂度提升，是典型的以空间换时间的操作。
    public static void main(String[] args) {
        Integer[] array = {4,6,8,7,9,2,10,1};
        sort(array);
        System.out.println(Arrays.toString(array));
    }
}
